package lc;

import static ch2linkedlist.Chapter.createSampleList;
import ch2linkedlist.Chapter;
import ch2linkedlist.ListNode;

public class SortLinkedList {
    public ListNode sortList(ListNode head) {
    	int count = 0;
    	ListNode n = head;
    	while (n != null) {
    		count++;
    		n = n.next;
    	}
    	
    	if (count == 0) {
    		return head;
    	}
    	else {
    		return mergeSort(head, count);
    	}
    }

    ListNode mergeSort(ListNode head, int n) {
    	if (n == 1) {
    		return head;
    	}
    	
    	int m = n/2;
    	ListNode q = head;
    	for (int i=0; i<m; i++) {
    		q = q.next;
    	}
    	ListNode p = mergeSort(head, m);
    	ListNode r = mergeSort(q, n-m);
    	ListNode newHead = new ListNode(Integer.MAX_VALUE);
    	ListNode s = newHead;
    	int i1=0, i2=0;
    	while (i1 < m || i2 < n-m) {
    		int pval = i1 == m ? Integer.MAX_VALUE : p.val;
    		int rval = i2 == n-m ? Integer.MAX_VALUE : r.val;
    		if (pval < rval) {
    			s.next = new ListNode(pval);
    			p = p.next;
    			i1++;
    		}
    		else {
    			s.next = new ListNode(rval);
    			r = r.next;
    			i2++;
    		}
			s = s.next;
    	}
    	return newHead.next;
    }
    
    public static void main(String ...strings) {
    	SortLinkedList sol = new SortLinkedList();
		ListNode head = Chapter.createSampleList(new int [] {3, 1, 4, 2});
		ListNode sortList = sol.sortList(head);
		Chapter.print(sortList);
    }
}
